Polygon meshes are widely used in computer aided geometric design, geometric modeling, and computer graphics to represent surfaces in digital form. Polygon meshes are described in detail in U.S. Pat. No. 5,506,947 “Curve and Surface Smoothing Without Shrinkage,” by G. Taubin, and in the paper “A Signal Processing Approach To Fair Surface Design,” by G. Taubin, Siggraph'95 Conference Proceedings, August 1995, pages 351-358, both are here incorporated herein by reference in entirety for all purposes. A polygon mesh includes a polygon mesh connectivity and a primal mesh signal. As used herein a primal mesh is the same as a polygon mesh.
A polygon mesh connectivity includes a plurality of polygon mesh vertices, and polygon mesh faces. Each polygon mesh face has three or more corners. Each corner is one of the polygon mesh vertices. Every mesh face is said to be “supported by” its corners. A polygon mesh edge is an unordered pair of mesh vertices that are consecutive in at least one polygon mesh face, in which case the polygon mesh edge is said to be “on the boundary” of the polygon mesh face, and “to join” the two polygon mesh vertices, and the polygon mesh face is said to be “incident” to the polygon mesh edge. One or more polygon mesh faces may be incident to the same polygon mesh edge. A regular edge is a polygon mesh edge with exactly two incident polygon mesh faces. FIG. 1 shows a polygon mesh with vertices 110, edges 120, and faces 130.
A graph is composed of a plurality of graph vertices and graph edges, with each graph edge being an unordered pair of graph vertices. Graphs are well known to those skilled of the prior art. The dual graph of a polygon mesh connectivity is a graph with the polygon mesh faces as dual graph vertices, and a plurality of dual graph edges, with each dual graph edge corresponding to a particular regular edge of the polygon mesh connectivity, and composed of the two polygon mesh faces which the regular edge is incident to. A regular mesh vertex is a polygon mesh vertex such that the polygon mesh faces incident to it form a cycle in the dual graph. The dual mesh connectivity of a polygon mesh connectivity includes a plurality of dual mesh vertices and dual mesh faces. The dual mesh vertices are the polygon mesh faces, and the dual mesh faces are the cycles of polygon mesh faces corresponding to the regular mesh vertices. The dual corners of a dual mesh face are the polygon mesh faces which have the regular mesh vertex as corner in the polygon mesh connectivity. The polygon mesh connectivity from which the dual mesh connectivity is generated is also called the primal mesh connectivity, and the polygon mesh vertices and faces are called primal mesh vertices and faces, respectively. The regular edges of a primal mesh are also called regular primal edges. The regular edges of a dual mesh are also called regular dual edges. It is known in the prior art that there is a one-to-one correspondence between regular primal edges and regular dual edges.
FIG. 2 shows a portion of a primal mesh 200 and a corresponding portion of its dual mesh 220, and the relations existing among their vertices, edges, and faces. Every primal vertex 210 of the primal mesh 200 corresponds to a dual face 230 of the dual mesh 220. Every primal face 215 of the primal mesh 200 corresponds to a dual vertex 235 of the dual mesh 220. Every regular primal edge 216 of the primal mesh 200 joining primal vertices 217 and 218 of the corresponds to one regular dual edge 226 joining dual vertices 227 and 228.
FIG. 3a illustrates the correspondence between regular primal edges and regular dual edges. Each regular primal edge 300 corresponds to a regular dual edge 310. The regular primal edge 300 joins primal vertices 320 and 330. The regular dual edge 310 joins dual vertices 340 and 350 corresponding to primal faces 360 and 370 of the primal mesh, respectively. FIG. 3b shows a primal vertex 365, the primal mesh faces 366, 367, 368, 369, and 370 incident to the primal mesh vertex 365, forming a cycle 371 in the dual graph, and joined by regular primal edges 380, 381, 382, 383, and 384.
A polygon mesh connectivity is called manifold without boundary when all its polygon mesh vertices and polygon mesh edges are regular. The construction of the dual mesh connectivity from a polygon mesh connectivity can be regarded as an operator operating on the family of all the polygon mesh connectivities. We call this operator dual mesh operator. It is known that when the dual mesh operator is applied to the dual mesh connectivity of a primal mesh connectivity, a polygon mesh connectivity equivalent to the primal mesh connectivity is obtained if and only if the primal mesh connectivity is manifold without boundary. Data structures to represent the primal and dual mesh connectivities of a manifold without boundary polygon mesh are described in the prior art.
A primal mesh signal is composed of primal points. Each primal point is a point in a N-dimensional space and corresponds to one of the polygon mesh vertices of the polygon mesh connectivity. These primal points of a primal mesh signal may represent different properties of the polygon mesh, such as vertex positions which define the geometry of the polygon mesh, color vectors, normal vectors, and texture coordinates used to generate pictures of the shape represented by the polygon mesh. The primal points of a primal mesh signal may also represent physical properties such as temperature or mechanical strain forces associated with numerical simulations.
A dual mesh signal is composed of dual points. Each dual point is a point in the same N-dimensional space and corresponds to one polygon mesh face of the polygon mesh connectivity. The dual points of the dual mesh signal are usually computed as a function of the primal points of a primal mesh signal. The barycenter dual signal is a dual mesh signal where each dual point is computed as the face barycenter or average of the primal points associated with the corners of the corresponding primal mesh face. The barycenter dual mesh of a polygon mesh is composed of the dual mesh connectivity of the polygon mesh connectivity and the barycenter dual signal of the primal mesh signal.
The approximation of a smooth surface embedded in N-dimensional space by a polygon mesh can be regarded as the analog to digital conversion process in signal processing, where the polygon mesh connectivity extends the classical notion of regular resampling to the irregular setting. Sometimes it is necessary to change the resampling rate of a given input digital signal, and it is desirable to do so directly in the digital domain, without reconstructing the analog signal. Such processes that produce an output digital signal directly from an input digital signal as referred to in the prior art as resampling processes. The input digital signal to a resampling process is also called resampled signal, and the output digital signal is also called resampled signal. When such a resampling process is performed, it is important to prevent signal degradation. Well-established methods exist in the prior art to resample signals defined on regular grids, but no extensions are known for signals defined on irregular polygon meshes. One way to measure signal degradation is to apply the same resampling process to the resampled signal to obtain a new digital signal at the original resampling rate, and then compare this new digital signal with the resampled signal. The construction of the barycenter dual mesh of a polygon mesh can be regarded as a resampling operator. The square of this operator produces new primal points on the vertices of the original resampled polygon mesh. The problem is that this resampling process produces significant signal loss. In fact, if the barycenter dual mesh operator is applied iteratively, over and over again, all the primal and dual points converge simultaneously to a single point in N-dimensional space, i.e., to a constant signal. The mathematical details are explained in the paper “Dual Mesh Resampling,” by G. Taubin, Pacific Graphics Conference Proceedings, Tokyo, Japan, October 2001, which is here incorporated by reference in its entirety for all purposes.
Sometimes polygon meshes are constructed as the result of measurements performed by a three-dimensional camera, laser scanner, CAT scanner, or other three-dimensional shape measurement device. These polygon meshes approximate the topology and geometry of a physical object, as opposed of a virtual object created in a computer without a physical realization. Data obtained as a result of physical measurements contain noise. Mesh smoothing algorithms are used to remove the noise from the geometry of polygon meshes. Most mesh smoothing algorithms derive from Laplacian smoothing. Laplacian smoothing, as well as an extension that solves the problem of shrinkage, is described in the papers cited above, “A Signal Processing Approach To Fair Surface Design,” by G. Taubin, Siggraph'95 Conference Proceedings, August 1995, pages 351-358, and in U.S. Pat. No. 5,506,947 “Curve and Surface Smoothing Without Shrinkage,” by G. Taubin. A number of other enhancements to Laplacian smoothing have been introduced in recent years to try to overcome some of its limitations. Despite these improvements existing polygon mesh smoothing processes lack sufficient balance between amount of smoothing and speed of the smoothing process.
Subdivision surfaces have become a popular type of prior art polygon meshes used in modeling and animation. A subdivision surface is a smooth surface obtained as the limit of an infinite sequence of polygon meshes, where the next polygon mesh in the sequence is obtain from its predecessor by first refining the connectivity, and then computing appropriate vertex positions on the vertices of the refined connectivity as a function of the vertex positions of the coarse connectivity. The computation of refined vertex positions is usually a two step process, with a first linear interpolation step, and a second smoothing step. A subdivision polygon mesh is a polygon mesh obtained by applying a finite number of refinement operations to a base polygon mesh. The most popular subdivision schemes are those proposed by Loop in “Smooth Subdivision Surfaces Based on Triangles,” by C. Loop, Master Thesis, Dept. of Mathematics, University of Utah”, August “1987”; by Catmull and Clark in the paper “Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes,” by E. Catmull, and J. Clark, CAD, volume 10, pages 350-355, 1978, and by Doo and Sabin in the paper “Behavior of Recursive Division Surfaces Near Extraordinary Points”, by D. Doo, and M. Sabin, CAD, volume 10, pages 356-360, 1978. More recent advances in this area are described in “Course 23: Subdivision for Modeling and Animation,” by D. Zorin and P. Schröder (eds.), Siggraph'2000 Course Notes, July 2000. One remaining problem with subdivision surfaces is that the number of polygon mesh faces increases to fast in the sequence of polygon meshes. For example, both in Loop's and Catmull-Clark schemes the number of faces grows by a factor of four from one polygon mesh of the sequence to the next. It is desirable to design subdivision schemes where the number of faces grows less rapidly. One such scheme for triangle meshes is described in the paper “Square Root of 3 Subdivision,” by L. Kobbelt, Siggraph'2000 Conference Proceedings, pages 103-112, July 2000. It is known that the connectivity refinement operator of the Catmull-Clark scheme has a square root. Herein, disclosure we will call this operator the primal-dual connectivity refinement operator. The number of faces grows approximately by two when the primal-dual connectivity refinement operator is used to refine the connectivity. The problem is that no method has been proposed to properly refine the geometry, i.e., to determine the vertex positions of the refined connectivity in such a way that the smoothness increases with the sequence of polygon meshes.
When the primal-dual connectivity refinement operator is applied to a primal mesh connectivity, a primal-dual mesh connectivity is produced. The primal-dual mesh connectivity is composed of primal-dual mesh vertices and primal-dual mesh faces. Each primal-dual vertex is either a primal mesh vertex or a primal mesh face. Each prima-dual face corresponds to one particular regular edge of the primal mesh connectivity. The corners of the primal-dual face are the two primal mesh vertices that the regular edge joins and the two primal mesh faces incident to the regular edge.
FIG. 4 illustrates the construction of the primal-dual mesh connectivity on a portion of a primal mesh connectivity 400. In a first step, for each primal mesh face 405, one primal-dual vertex 435 is created, and the primal mesh face 405 is subdivided into triangles 436, 437, 438, 439, and 440, by connecting the primal-dual vertex 435 to the corners 406, 407, 408, 409, and 410 of the primal mesh face 405. The result of this first step is a new polygon mesh connectivity 430, where all the new polygon mesh faces are triangular. In a second step, the edges of the primal mesh connectivity are removed from the new polygon mesh connectivity resulting in a into a quadrilateral face 465 obtained by joining the two triangular faces 438 and 441 incident to the primal edge 442. The resulting primal-dual mesh connectivity 460 is composed of primal dual faces which are all quadrilateral.